Las listas de Python en el nivel inferior no son listas enlazadas sueltas, sino altamente organizadas ArrayListSu verdad fundamental es que ocupa un espacio contiguo de direcciones en la memoria. Aquí no se almacena el objeto en sí, sino una referencia al objeto referencia(en el nivel del lenguaje C, esto es un puntero). Este diseño permite una gestión unificada de datos heterogéneos, ya sean tuplas de colores primarios (RGB) o claves criptográficas complejas (Key), todas ocupan solo un tamaño fijo de puntero.
Matemáticas de direccionamiento y equilibrio de rendimiento
- $O(1)$ acceso aleatorioUtilizando la fórmula $\text{dirección del elemento} = \text{dirección inicial} + \text{índice} \times \text{tamaño}$, la CPU puede localizar instantáneamente.
- Análisis amortizado (Amortized Analysis)Utilizando una estrategia de asignación excesiva, aunque la inserción individual podría ser $O(n)$, pero $\text{costo total} = n + \sum_{j=0}^{\lg n} 2^j = 3n$, lo que garantiza un rendimiento promedio de $O(1)$ para añadir elementos.
- Límite de inserciónComo se muestra en la Figura 8-2, insertar en cualquier posición requiere desplazar todos los punteros posteriores, con una complejidad de $O(n)$.
Comparación de algoritmos
A diferencia del índice de ArrayList ($O(1)$), el tiempo de búsqueda en una lista saltada (Skip List) tiene una complejidad de $O(\log n)$. Y el fundamento del algoritmo RSA —el algoritmo de Euclides— radica en $gcd(a,0)=a$. Estos algoritmos operan en este pequeño espacio de memoria.